package datastructure;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class LinkTree<T> {

	
	T node;
	private List<LinkTree<T>> children;
	
	public LinkTree(T node){
		this.node=node;
	}
	
	public boolean addChild(LinkTree<T> child){
		if(children==null){
			children= new ArrayList<LinkTree<T>>();
		}
		return children.add(child);
	}
	
	public boolean removeChild(LinkTree<T> child){
		if(children==null||children.size()<1){
			return true;
		}
		return children.remove(child);
	}
	
	public List<LinkTree<T>> getChildren(){
		return children;
	}
	
	public void traverse(){
		traverse(this);
	}
	
	public void traverse(LinkTree<T> node){
		if(node.node!=null){
			System.out.println(node.toString());
		}
		if(node.children!=null){
			for(LinkTree<T> child:node.children){
				if(child.node!=null){
					if(child.children==null){
						System.out.println(child.toString());
					}else{
						traverse(child);
					}
				}
			}
		}
	}
	
	public int getNodesCount(){
		return getNodesCount(this);
	}
	
	public int getNodesCount(LinkTree<T> node){
		if(node.children!=null){
			int count = 1;
			for(LinkTree<T> child:node.children){
				count=count+getNodesCount(child);
			}
			return count;
		}
		return 1;
	}
	public int getDeep(){
		return getDeep(this);
	}
	public int getDeep(LinkTree<T> node){
		if(node.children!=null){
			int i = node.children.size();
			int[] deepArray = new int[i];
			for(int j=0;j<i;j++){
				deepArray[j]=getDeep(node.children.get(j));
			}
			int deep=deepArray[0];
			for(int max:deepArray){
				if(max>deep){
					deep=max;
				}
			}
			return deep+1;
		}
		return 1;
	}
	
	
	public void breadedTraverser(){
		breadedTraverser(this);
	}
	
	public void breadedTraverser(LinkTree<T> node){
		List<LinkTree<T>> list = new ArrayList<LinkTree<T>>();
		Queue<LinkTree<T>> treeQueue = new ArrayDeque<LinkTree<T>>();
		if(node!=null){
			treeQueue.offer(node);
		}
		while(!treeQueue.isEmpty()){
			list.add(treeQueue.peek());
			LinkTree<T> nodeNext = treeQueue.poll();
			if(nodeNext.children!=null){
				for(LinkTree<T> child:nodeNext.children){
					treeQueue.offer(child);
				}
			}
		}
		for(LinkTree<T> tree:list){
			System.out.println(tree.toString());
		}
	}
	
	public String toString(){
		return node.toString();
	}
}
